/**
 * 
 */
package estructuras;

import java.util.ArrayList;
import java.util.List;


/**
 * @author byron
 *
 */
public class Arbol23<Generic extends Comparable<Generic>> implements ArbolInterfaz<Generic> {
	
	// Variables y objetos de instancia
	Arbol23<Generic> parent, left, right, center;
	Generic node1, node2;
	boolean permiteRepetidos = false;
	
	public Arbol23() {
		// Inicializar variables de instancia 
		setLeft(null);
		setRight(null);
		setCenter(null);
		setNode1(null);
		setNode2(null);
	}
	
	public Arbol23(Generic node1) {
		// Inicializar variables de instancia 
		setLeft(null);
		setRight(null);
		setCenter(null);
		setNode1(node1);
		setNode2(null);
	}
	
	public Arbol23(Generic node1, Generic node2) {
		// Inicializar variables de instancia 
		setLeft(null);
		setRight(null);
		setCenter(null);
		setNode1(node1);
		setNode2(node2);
	}
	
	public Arbol23<Generic> getParent() {
		return parent;
	}
	
	public void setParent(Arbol23<Generic> parent) {
		this.parent = parent;
	}
	
	public Arbol23<Generic> getLeft() {
		return left;
	}
	
	public void setLeft(Arbol23<Generic> left) {
		if(left != null)
			left.setParent(this);
		this.left = left;
	}
	
	private Arbol23<Generic> getCenter() {
		return center;
	}
	
	public void setCenter(Arbol23<Generic> center) {
		if(center != null)
			center.setParent(this);
		this.center = center;
	}
	
	public Arbol23<Generic> getRight() {
		return right;
	}
	
	public void setRight(Arbol23<Generic> right) {
		if(right != null)
			right.setParent(this);
		this.right = right;
	}
	
	public Generic getNode1() {
		return node1;
	}
	
	public void setNode1(Generic node1) {
		this.node1 = node1;
	}
	
	public Generic getNode2() {
		return node2;
	}
	
	public void setNode2(Generic node2) {
		this.node2 = node2;
	}
	
	@Override
	public void add(Generic object) {
		if((permiteRepetidos) || ((!permiteRepetidos) && (find(object) == null))) {
			add(new Arbol23<Generic>(object));
		}
	}
	
	private void add(Arbol23<Generic> arbol) {
		// Verificar si este es un arbol vacio o si es una hoja
		if((node1 == null) || (getLeft() == null)) {
			// Cuando el arbol esta vacio
			addInsert(arbol);
		} else {
			int caso1 = node1.compareTo(arbol.getNode1());
		
			if(getCenter() != null) {
				int caso2 = node2.compareTo(arbol.getNode1());
		
				// Verificar a donde bajar
				if(caso1 >= 0) {
					getLeft().add(arbol);
				} else if((caso1 < 0) && (caso2 >= 0)) {
					getCenter().add(arbol);
				} else if((caso1 < 0) && (caso2 < 0)) {
					getRight().add(arbol);
				}
				
			} else {
				// Verificar a donde bajar
				if(caso1 >= 0) {
					getLeft().add(arbol);
				} else {//if(caso1 < 0) {
					getRight().add(arbol);
				}
			}
		}
		//System.out.println(show());
	}
	
	private void addInsert(Arbol23<Generic> arbol) {
		
		// Verificar si este es un arbol vacio
		if(node1 == null) {
			// Cuando el arbol esta vacio
			node1 = arbol.getNode1();
			setLeft(arbol.getLeft());
			//setCenter(arbol.getCenter());
			setRight(arbol.getRight());
			
		} else if (node2 == null) {
			// Verificar si el segundo nodo esta disponible
			int caso = node1.compareTo(arbol.getNode1());
			
			if(caso < 0) {
				node2 = arbol.getNode1();
				if((arbol.getRight() != null) || (arbol.getLeft() == null)) {
					setCenter(arbol.getLeft());
					setRight(arbol.getRight());					
				}
			} else {
				node2 = node1;
				node1 = arbol.getNode1();
				if((arbol.getLeft() != null) || (arbol.getRight() != null)) {
					setLeft(arbol.getLeft());
					setCenter(arbol.getRight());
				}
			}
			
			/*
		} else if((node1.compareTo(arbol.getNode1()) == 0) || 
				(node2.compareTo(arbol.getNode1()) == 0)){
			// Revisar si se debe guardar
			if(permiteRepetidos) {
				if(getNode2() == null) {
					node2 = arbol.getNode1();
				} else {
					addSplit(arbol);
				}
			}
			*/
		}  else {
			addSplit(arbol);
		}
	}
	
	private void addSplit(Arbol23<Generic> arbol) {
		
		// Declarar variables y objetos
		Arbol23<Generic> p = null,
			l = new Arbol23<Generic>(),
			r = new Arbol23<Generic>(),
			c = new Arbol23<Generic>();
		
		// Encontrar el mas pequeño, el mediano y el grande
		int caso1 = node1.compareTo(arbol.getNode1()),
			caso2 = node2.compareTo(arbol.getNode1()),
			caso3 = node1.compareTo(node2);
		
		if((caso3 == 0) && (caso2 == 0)) {
			// 1 <= o < 2
			l.setNode1(node1);
			c.setNode1(arbol.getNode1());
			r.setNode1(node2);
			
			l.setLeft(getLeft());
			l.setRight(arbol.getLeft());
			r.setLeft(arbol.getRight());
			r.setRight(getRight());
		} else if(caso1 < 0) {
//	  		if (caso3 <= 0) {
				l.setNode1(node1);
				if(caso2 > 0) {
					// 1 <= o < 2
					c.setNode1(arbol.getNode1());
					r.setNode1(node2);
					
					l.setLeft(getLeft());
					l.setRight(arbol.getLeft());
					r.setLeft(arbol.getRight());
					r.setRight(getRight());
				} else {
					// 1 < 2 < o
					c.setNode1(node2);
					r.setNode1(arbol.getNode1());
					//r.setNode1(arbol.getNode1());
					
					l.setLeft(getLeft());
					l.setRight(getCenter());
					r.setLeft(arbol.getLeft());
					r.setRight(arbol.getRight());
				}
//			} 
		} else {
//			if (caso3 < 0) {
				// o < 1 < 2
				// l.setNode1(arbol.getNode1());
				l.setNode1(arbol.getNode1());
				c.setNode1(node1);
				r.setNode1(node2);
				
				l.setLeft(arbol.getLeft());
				l.setRight(arbol.getRight());
				r.setLeft(getCenter());
				r.setRight(getRight());
//			} 
		}
		
		// Modificar arbol principal
		c.setLeft(l);
		c.setRight(r);
		
		// Insertar el nuevo dato si no causa conflicto
		if(getParent() == null) {
			p = new Arbol23<Generic>();
			//lugar = "V";
		} else {
			p = getParent();			
		}
		
		p.addInsert(c);
		
		setParent(p.getParent());
		setLeft(p.getLeft());
		setNode1(p.getNode1());
		setCenter(p.getCenter());
		setNode2(p.getNode2());
		setRight(p.getRight());
	}
	
	@Override
	public String show() {
		// Crear la cadena de texto que contiene los numeros en orden ascendente
		String cadena = 
			"(L{" + ((left != null) ? left.show() : "") +
			"} 1{" + ((node1 != null) ? node1 : "") + 
			"} C{" + ((center != null) ? center.show() : "") + 
			"} 2{" + ((node2 != null) ? node2 : "") +
			"} R{" + ((right != null) ? right.show() : "") + 
			"})";
		
		/*/ Eliminar espacios en blanco
		String resp = "";
		char ant = ' ';
		for(int i =0; i < cadena.length(); i++){
			char cur = cadena.charAt(i);
			
			if(((ant == ' ') && (cur == ' ')) || (ant == ',') ) {
				// DO NOTHING
				ant = cur;
				continue;
			} else if(cur == ',') {
				resp += ", ";
			} else if(cur == ' ') {
				resp += ", ";
			} else {
				resp += cur;
			}
			
			ant = cur;
		}
		return resp;
		//*/
		
		return cadena;
		
		/*
		return ("(" + ((left != null) ? left.mostrar() : "") +
				" " + ((node1 != null) ? node1 : "") +
				" " + ((center != null) ? center.mostrar() : "") + 
				" " + ((node2 != null) ? node2 : "") +
				" " + ((right != null) ? right.mostrar() : "") +
				")");
		*/
	}

	@Override
	public void remove(Generic object) {
		Arbol23<Generic> nodo = find(object), leafNode = null;
		
		// Revisar que el objeto a eliminar exista en el árbol
		if(nodo == null)
			return;
		
		// Revisar si está en una hoja o no 
		if(nodo.getLeft() == null)
			// Está en una hoja
			leafNode = nodo;
		else {
			// No está en una hoja, cambiarlo con siguiente elemento en la 
			// secuencia en orden (una hoja)	
			if(nodo.getNode1().compareTo(object) == 0) {
				// Primer nodo
				if(nodo.getNode2() == null) {
					// derecha primer nodo
					Generic tmp = nodo.getNode1();
					nodo.setNode1(nodo.getRight().getNode1());
					nodo.getRight().setNode1(tmp);
					leafNode = nodo.getRight();
				} else {
					// centro primer nodo
					Generic tmp = nodo.getNode1();
					nodo.setNode1(nodo.getCenter().getNode1());
					nodo.getCenter().setNode1(tmp);
					leafNode = nodo.getCenter();
				}
			} else if(nodo.getNode2().compareTo(object) == 0) {
				// Segundo nodo (derecha primer nodo)
				Generic tmp = nodo.getNode2();
				nodo.setNode2(nodo.getRight().getNode1());
				nodo.getRight().setNode1(tmp);
				leafNode = nodo.getRight();
			}
		}
		
		// Eliminar el objeto de la hoja **
		if(leafNode.getNode1().compareTo(object) == 0) {
			leafNode.setNode1(null);
			if(leafNode.getNode2() != null) {
				leafNode.setNode1(leafNode.getNode2());
				leafNode.setNode2(null);
			}
		} else {
			leafNode.setNode2(null);
		}
		
		// Si la hoja modificada se quedo sin nodos internos (quitarla)
		if((leafNode.getNode1() == null) && (leafNode.getNode2() == null))
			fix(leafNode);
	}
	
	/**
	 * 
	 * 
	 * @param object
	 */
	private void fix(Arbol23<Generic> nodo) {
		// Verificar si es el root (la raíz)
		if(nodo.getParent() == null) {
			// Es la raiz, quitarla y poner la nueva
			// Encontrar nueva raiz
			Arbol23<Generic> nuevaRaiz = null;
			if((getLeft() != null) && (getLeft().getNode1() != null)) {
				nuevaRaiz = getLeft();
			} else if((getCenter() != null) && (getCenter().getNode1() != null)) {
				nuevaRaiz = getCenter();
			} else if((getRight() != null) && (getRight().getNode1() != null)) {
				nuevaRaiz = getRight();
			}
			
			// Cambiar raíz
			if(nuevaRaiz != null){
				setLeft(nuevaRaiz.getLeft());
				setNode1(nuevaRaiz.getNode1());
				setCenter(nuevaRaiz.getCenter());
				setNode2(nuevaRaiz.getNode2());
				setRight(nuevaRaiz.getRight());
			}
		} else {
			// No es la raiz, obtener a papa y mayores
			Arbol23<Generic> p = nodo.getParent();
			
			// Caso 1 (es nodo derecho, separar)
			if((p.getNode2() == null) && (p.getRight() == nodo) && (p.getLeft().getNode1() != null) && 
					(p.getLeft().getNode2() != null)) {
				// Cambiar nodos
				nodo.setNode1(p.getNode1());
				p.setNode1(p.getLeft().getNode2());
				p.getLeft().setNode2(null);
				// Cambiar cosas arboles
				nodo.setRight(nodo.getCenter());
				nodo.setCenter(null);
				nodo.setLeft(p.getLeft().getRight());
				p.getLeft().setRight(p.getLeft().getCenter());
				p.getLeft().setCenter(null);
			}
			// Caso 2 (es nodo izquierdo, separar)
			else if((p.getNode2() != null) && (p.getLeft() == nodo) && (p.getCenter().getNode1() != null) && 
					(p.getCenter().getNode2() != null)) {
				// Cambiar nodos
				nodo.setNode1(p.getNode1());
				p.setNode1(p.getCenter().getNode1());
				p.getCenter().setNode1(p.getNode2());
				p.getCenter().setNode2(null);
				// Cambiar cosas arboles
				nodo.setLeft(nodo.getCenter());
				nodo.setCenter(null);
				nodo.setRight(p.getCenter().getLeft());
				p.getCenter().setLeft(p.getCenter().getCenter());
				p.getCenter().setCenter(null);
			} else if((p.getNode2() == null) && (p.getRight() == nodo) && (p.getLeft().getNode1() != null) && 
						(p.getLeft().getNode2() == null)) {
				// Caso 3 (es nodo derecho, unir)
					// Cambiar nodos
					p.getLeft().setNode2(p.getNode1());
					p.setNode1(null);
					// Cambiar cosas arboles
					p.getLeft().setCenter(p.getLeft().getRight());
					p.getLeft().setRight(nodo.getCenter());
					p.setCenter(p.getLeft());
					p.setLeft(null);
					p.setRight(null);
			} else if((p.getNode2() != null) && (p.getLeft() == nodo) && (p.getCenter().getNode1() != null) && 
					(p.getCenter().getNode2() == null)) {
			// Caso 4 (es nodo izquierdo, unir)
				// Cambiar nodos
				nodo.setNode1(p.getNode1());
				nodo.setNode2(p.getCenter().getNode1());
				p.setNode1(p.getNode2());
				p.setNode2(null);
				// Cambiar cosas arboles
				nodo.setLeft(nodo.getCenter());
				nodo.setCenter(p.getCenter().getLeft());
				nodo.setRight(p.getCenter().getRight());
				p.setCenter(null);
			} else if((p.getNode2() != null) && (p.getLeft() == nodo) && (p.getCenter().getNode1() != null) && 
					(p.getCenter().getNode2() != null) && (p.getLeft().getNode1() != null) && (p.getLeft().getNode2() != null)) {
			// Caso 5 (es nodo izquierdo, unir - muchos nodos)
				// Cambiar nodos
				nodo.setNode1(p.getNode1());
				p.setNode1(p.getCenter().getNode1());
				p.getCenter().setNode1(p.getNode2());
				p.setNode2(p.getRight().getNode1());
				p.getRight().setNode1(p.getRight().getNode2());
				p.getRight().setNode2(null);
				// Cambiar cosas arboles
				nodo.setLeft(nodo.getCenter());
				nodo.setCenter(null);
				nodo.setRight(p.getCenter().getLeft());
				p.getCenter().setLeft(p.getCenter().getRight());
				p.getCenter().setRight(p.getRight().getLeft());
				p.getRight().setLeft(p.getRight().getCenter());
				p.getCenter().setCenter(null);
			} else if((p.getNode2() != null) && (p.getCenter() == nodo) && (p.getRight().getNode1() != null) && 
					(p.getRight().getNode2() != null)) {
			// Caso 6 (es nodo centro, mover - muchos nodos)
				// Cambiar nodos
				nodo.setNode1(p.getNode2());
				p.setNode2(p.getRight().getNode1());
				p.getRight().setNode1(p.getRight().getNode2());
				p.getRight().setNode2(null);
				// Cambiar cosas arboles
				nodo.setLeft(nodo.getCenter());
				nodo.setCenter(null);
				nodo.setRight(p.getRight().getLeft());
				p.getRight().setLeft(p.getRight().getCenter());
				p.getCenter().setCenter(null);
			} else if((p.getCenter() == nodo) && (p.getLeft().getNode1() != null) && 
				(p.getRight().getNode2() == null)) {
			// Caso 7 (es nodo centro, mover - pocos nodos)
				// Cambiar nodos
				p.getLeft().setNode2(p.getNode1());
				p.setNode1(p.getNode2());
				p.setNode2(null);
				p.getLeft().setCenter(p.getLeft().getRight());
				// Cambiar cosas arboles
				p.getLeft().setRight(nodo.getCenter());
				p.setCenter(null);
			} else if((p.getNode2() == null) && (p.getLeft() == nodo) && (p.getRight().getNode1() != null) && 
						(p.getRight().getNode2() != null)) {
				// Caso 1-5 
					// Cambiar nodos
					nodo.setNode1(p.getNode1());
					p.setNode1(p.getRight().getNode1());
					p.getRight().setNode1(p.getRight().getNode2());
					p.getRight().setNode2(null);
					// Cambiar cosas arboles
					nodo.setLeft(nodo.getCenter());
					nodo.setCenter(null);
					nodo.setRight(p.getRight().getLeft());
					p.getRight().setLeft(p.getRight().getCenter());
					p.getLeft().setCenter(null);
			} else if((p.getNode2() == null) && (p.getLeft() == nodo) && (p.getRight().getNode1() != null) && 
					(p.getRight().getNode2() == null)) {
			// Caso 2-5 (es nodo derecho, unir)
				// Cambiar nodos
				p.getRight().setNode2(p.getNode1());
				p.setNode1(null);
				// Cambiar cosas arboles
				p.getRight().setCenter(p.getRight().getLeft());
				p.getRight().setLeft(nodo.getCenter());
				p.setCenter(p.getLeft());
				p.setLeft(null);
				p.setRight(null);
			} else if((p.getNode2() == null) && (p.getRight() == nodo) && (p.getLeft().getNode1() != null) && 
							(p.getLeft().getNode2() == null)) {
					// Caso 3 (es nodo derecho, unir)
						// Cambiar nodos
						p.getLeft().setNode2(p.getNode1());
						p.setNode1(null);
						// Cambiar cosas arboles
						p.getLeft().setCenter(p.getLeft().getRight());
						p.getLeft().setRight(nodo.getCenter());
						p.setCenter(p.getLeft());
						p.setLeft(null);
						p.setRight(null);
				} else if((p.getNode2() != null) && (p.getLeft() == nodo) && (p.getCenter().getNode1() != null) && 
						(p.getCenter().getNode2() == null)) {
				// Caso 4 (es nodo izquierdo, unir)
					// Cambiar nodos
					nodo.setNode1(p.getNode1());
					nodo.setNode2(p.getCenter().getNode1());
					p.setNode1(p.getNode2());
					p.setNode2(null);
					// Cambiar cosas arboles
					nodo.setLeft(nodo.getCenter());
					nodo.setCenter(p.getCenter().getLeft());
					nodo.setRight(p.getCenter().getRight());
					p.setCenter(null);
				} else if((p.getNode2() != null) && (p.getLeft() == nodo) && (p.getCenter().getNode1() != null) && 
						(p.getCenter().getNode2() != null) && (p.getLeft().getNode1() != null) && (p.getLeft().getNode2() != null)) {
				// Caso 5 (es nodo izquierdo, unir - muchos nodos)
					// Cambiar nodos
					nodo.setNode1(p.getNode1());
					p.setNode1(p.getCenter().getNode1());
					p.getCenter().setNode1(p.getNode2());
					p.setNode2(p.getRight().getNode1());
					p.getRight().setNode1(p.getRight().getNode2());
					p.getRight().setNode2(null);
					// Cambiar cosas arboles
					nodo.setLeft(nodo.getCenter());
					nodo.setCenter(null);
					nodo.setRight(p.getCenter().getLeft());
					p.getCenter().setLeft(p.getCenter().getRight());
					p.getCenter().setRight(p.getRight().getLeft());
					p.getRight().setLeft(p.getRight().getCenter());
					p.getCenter().setCenter(null);
				} else if((p.getNode2() != null) && (p.getCenter() == nodo) && (p.getRight().getNode1() != null) && 
						(p.getRight().getNode2() != null)) {
				// Caso 6 (es nodo centro, mover - muchos nodos)
					// Cambiar nodos
					nodo.setNode1(p.getNode2());
					p.setNode2(p.getRight().getNode1());
					p.getRight().setNode1(p.getRight().getNode2());
					p.getRight().setNode2(null);
					// Cambiar cosas arboles
					nodo.setLeft(nodo.getCenter());
					nodo.setCenter(null);
					nodo.setRight(p.getRight().getLeft());
					p.getRight().setLeft(p.getRight().getCenter());
					p.getCenter().setCenter(null);
				} else if((p.getCenter() == nodo) && (p.getLeft().getNode1() != null) && 
					(p.getRight().getNode2() != null)) {
				// Caso 7 (es nodo centro, mover - muchos nodos)
					// Cambiar nodos
					p.getLeft().setNode2(p.getNode1());
					p.setNode1(p.getNode2());
					p.setNode2(null);
					// Cambiar cosas arboles
					p.getLeft().setCenter(p.getLeft().getRight());
					p.getLeft().setRight(nodo.getCenter());
					p.setCenter(null);
			}
			
			// Revisar si el padre esta vacio
			if((p.getNode1() == null) && (p.getNode2() == null)) {
				fix(p);
			}
		}		
	}

	@Override
	public boolean allowRepetitions() {
		return permiteRepetidos;
	}

	@Override
	public Arbol23<Generic> find(Generic objeto) {
		// Si esta vacia
		if(node1 == null)
			return null;
		
		// Si tiene un nodo
		int val1 =  node1.compareTo(objeto);
		if(val1 == 0)
			return this;
		else if(val1 < 0)
			return (left == null) ? null : left.find(objeto);
		else if((val1 > 0) && (node2 == null))
			return (right == null) ? null : right.find(objeto);
		else if(node2 != null) {
			int val2 =  node2.compareTo(objeto);
			if(val2 == 0)
				return this;
			else if((val1 > 0) && (val2 < 0))
				return (center == null) ? null : center.find(objeto);
			else if(val2 > 0)
				return (right == null) ? null : right.find(objeto);
		}
		
		// Regresar
		return null;
	}

	@Override
	public List<Generic> search(Generic objeto) {
		// Declarar variables y objetos
		List<Generic> lista = new ArrayList<Generic>();
		
		// Si esta vacia
		if(node1 == null)
			return lista;
		
		// Si tiene un nodo
		int val1 =  node1.compareTo(objeto);
		if(val1 == 0)
			lista.add(node1);
		
		// Agregar las de la izquierda y derecha 
		if(getLeft() != null)
			lista.addAll(left.search(objeto));
		if(getRight() != null)
			lista.addAll(right.search(objeto));
		
		// Nodo2 y centro 
		if(node2 != null) {
			int val2 =  node2.compareTo(objeto);
			if(val2 == 0)
				lista.add(node2);
			
			if(getCenter() != null)
				lista.addAll(center.search(objeto));
		}
		
		// Regresar
		return lista;
	}

	@Override
	public void setAllowRepetitions(boolean permitir) {
		permiteRepetidos = permitir;
	}	
}